package com.easy.leetcode.dp;

import java.util.Arrays;

//最长回文子串
public class LongestPalindrome5 {

    public String longestPalindrome(String s) {
        if (s.length()==1) {
            return s;
        }
        String res="";
        //dp定义，从i到j是否是回文串
        boolean[][] dp = new boolean[s.length()][s.length()];
        /*for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }*/
        //注意遍历顺序，由于推导公式 两个字符相等时，dp[i][j] 是由dp[i+1][j-1]推导出来的，所以需要先算出下一行的值，
        //所以需要倒序遍历
        for (int i = s.length()-1; i>= 0; i--   ) {
            for (int j = i; j <s.length(); j++) {
                //不等
                if (s.charAt(i)!=s.charAt(j)) {
                    dp[i][j]=false;
                }else {
                    if (j-i<=2) {
                        dp[i][j]=true;
                    }else {
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if (dp[i][j]){
                    if (j-i+1>res.length()){
                        res =s.substring(i,j+1);
                    }
                }
            }
        }
        for (int i = 0; i < s.length(); i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println(res);
        return res;
    }

    public static void main(String[] args) {
        LongestPalindrome5 longestPalindrome5 = new LongestPalindrome5();
        longestPalindrome5.longestPalindrome("ababd");
    }
}
